package main

import (
	"errors"
	"fmt"
)

type pos struct {
	x int
	y int
}

type Node struct {
	data *pos
	next *Node
}

type LinkStack interface {
	IsEmpty() bool
	Push(value string)
	Pop() (string, error)
	Length() int
}

func NewStack() *Node {
	return &Node{}
}

func (n *Node) IsEmpty() bool { //判断是否为空
	return n.next == nil
}
func (n *Node) Push(value *pos) {
	newnode := &Node{data: value} //初始化
	newnode.next = n.next
	n.next = newnode
}
func (n *Node) Pop() (*pos, error) {
	if n.IsEmpty() == true {
		return nil, errors.New("bug")
	}
	value := n.next.data
	n.next = n.next.next
	return value, nil
}
func (n *Node) Length() int {
	pnext := n
	length := 0
	for pnext.next != nil { //返回长度
		pnext = pnext.next
		length++
	}
	return length
}

const M = 10
const N = 10

var cangoout bool = false //假定走不出迷宫

//1代表人，2代表障碍，0空地

var data [M][N]int = [M][N]int{
	{1, 0, 2, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 2, 0, 0, 2, 0, 0, 0},
	{0, 0, 0, 0, 2, 0, 0, 2, 2, 0},
	{0, 0, 0, 0, 2, 0, 2, 0, 0, 0},
	{0, 0, 0, 0, 2, 0, 0, 0, 0, 2},
	{2, 2, 2, 0, 0, 2, 0, 2, 0, 0},
	{0, 0, 0, 0, 0, 2, 0, 2, 0, 2},
	{0, 0, 0, 0, 0, 0, 0, 2, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 2, 2, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 2, 0},
}

var AIdata [M][N]int = [M][N]int{
	{1, 0, 2, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 2, 0, 0, 2, 0, 0, 0},
	{0, 0, 0, 0, 2, 0, 0, 2, 2, 0},
	{0, 0, 0, 0, 2, 0, 2, 0, 0, 0},
	{0, 0, 0, 0, 2, 0, 0, 0, 0, 2},
	{2, 2, 2, 0, 0, 2, 0, 2, 0, 0},
	{0, 0, 0, 0, 0, 2, 0, 2, 0, 2},
	{0, 0, 0, 0, 0, 0, 0, 2, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 2, 2, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 2, 0},
}

func AIdataStack(AIdatax [M][N]int, i int, j int) bool {
	mystack := NewStack()
	mystack.Push(&pos{i, j})

	for !mystack.IsEmpty() {
		nowpos, err := mystack.Pop()

		if err != nil {
			break
		}

		i = nowpos.x
		j = nowpos.y

		AIdatax[i][j] = 3 //避免回头

		if i == N-1 && j == M-1 {
			cangoout = true
			AIdata = AIdatax
			fmt.Println("迷宫可以走出来")
			break
		} else {
			if j+1 <= M-1 && AIdatax[i][j+1] < 2 && cangoout != true {

				//AIout(AIdatax, i, j+1)
				mystack.Push(&pos{i, j + 1})
			}
			if i+1 <= N-1 && AIdatax[i+1][j] < 2 && cangoout != true {

				// AIout(AIdatax, i+1, j)
				mystack.Push(&pos{i + 1, j})
			}
			if j-1 >= 0 && AIdatax[i][j-1] < 2 && cangoout != true {

				///AIout(AIdatax, i, j-1)
				mystack.Push(&pos{i, j - 1})
			}
			if i-1 >= 0 && AIdatax[i-1][j] < 2 && cangoout != true {

				//AIout(AIdatax, i-1, j)

				mystack.Push(&pos{i - 1, j})
			}
		}

	}
	return cangoout
}

func main() {
	isok := AIdataStack(data, 0, 0)

	if isok {
		fmt.Println("可以走通")
		show(AIdata)
	} else {
		fmt.Println("没有路径")
	}
}
func show(arr [M][N]int) {
	for i := 0; i < M; i++ {
		for j := 0; j < N; j++ {
			fmt.Printf("%4d", arr[i][j])
		}
		fmt.Println("")
	}

}
